package bin_tree;



public class MyBinaryTree {
    //孩子兄弟表示法
    private static class Node{
           //不需要依托外部类对象
        private char val;
        private Node left;
        private Node right;
        public Node(char val){
            this.val = val;
        }
    }

    //生成一个测试二叉树
    public Node buidAtree(){
        Node nodeA = new Node('A');
        Node nodeB = new Node('B');
        Node nodeC = new Node('C');
        Node nodeD = new Node('D');
        Node nodeE = new Node('E');
        Node nodeF = new Node('F');
        Node nodeG = new Node('G');
        Node nodeH = new Node('H');
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeE.left = nodeG;
        nodeG.right = nodeH;
        nodeC.right = nodeF;
        return nodeA;
    }

    /**
     * 先序遍历-》根左右
     * 传入一个二叉树的根节点，根据先序遍历访问该树
     * @param root 根节点
     */
    public void preOrder(Node root){
        if(root == null){
            return;
        }
        //根节点先打印
        System.out.print(root.val + " ");
        //左树
        preOrder(root.left);
        //右树
        preOrder(root.right);
    }

    /**
     * 先序遍历-》左根右
     * @param root
     */
    public void inOrder(Node root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    /**
     * 后序遍历-》左右根
     * @param root
     */
    public void postOrder(Node root){
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    /**
     * 传入一个二叉树的根节点，求出该二叉树的节点个数
     * @param root 二叉树的根节点
     * @return 得到节点个数
     */
    public int getNodeCount(Node root){
        if (root == null){
            return 0;
        }
        return 1 + getNodeCount(root.left) + getNodeCount(root.right);
    }

    /**
     * 传入一棵二叉树的根节点root，就能求得该二叉树的叶子节点个数
     * @param root 传入根节点
     * @return 得到叶子节点个数
     */
    public int getLeafNodeCount(Node root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    /**
     * 传入一个根节点root,就能求得该树的高度
     * @param root 传入二叉树根节点
     * @return 得到二叉树的高度
     */
    public int height(Node root){
        if(root == null){
            return 0;
        }
        return 1 + Math.max(height(root.left),height(root.right));
    }

    /**
     * 判断一棵以root为根节点的二叉树中是否包含值为val的节点
     * @param root 二叉树的根节点
     * @param val 找val
     * @return 得到boolean值
     */
    public boolean contains(Node root,char val){
        if (root == null){
            return false;
        }
        if (root.val == val){
            return true;
        }
        return contains(root.left,val) || contains(root.right,val);
    }

    /**
     * 传入一棵二叉树二叉树的根节点root,求出第k层节点个数
     * @param root 二叉树的根节点
     * @param k 第k层
     * @return 得到节点个数
     */
    public int getKLevelNodes(Node root,int k){
        if (root == null || k == 0){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelNodes(root.left,k-1) + getKLevelNodes(root.right,k-1);
    }

    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        Node root = myBinaryTree.buidAtree();
        System.out.println("先序遍历结果:");
        myBinaryTree.preOrder(root);
        System.out.println();
        System.out.println("-----------------");
        System.out.println("中序遍历结果:");
        myBinaryTree.inOrder(root);
        System.out.println();
        System.out.println("------------------");
        System.out.println("后序遍历结果:");
        myBinaryTree.postOrder(root);
        System.out.println("二叉树节点个数为:");
        System.out.println(myBinaryTree.getNodeCount(root));
        System.out.println("二叉树的叶子节点个数为:");
        System.out.println(myBinaryTree.getLeafNodeCount(root));
        System.out.println("二叉树的高度为:");
        System.out.println(myBinaryTree.height(root));
        System.out.println(myBinaryTree.contains(root,'H'));
        System.out.println(myBinaryTree.contains(root,'X'));
        System.out.println("二叉树第4层节点个数:");
        System.out.println(myBinaryTree.getKLevelNodes(root,4));
    }
}
